package cn.z2huo.algorithm.sort.insert.shell;

import java.util.Arrays;

/**
 * 希尔排序，又称缩小增量排序，也是属于插入排序类的方法，但是在时间效率上较前几种排序方法有较大改进。
 * 作者： 张一卓
 * 时间： 2020/1/10 19:42
 */
public class ShellSorting {
    public int[] sort(int[] array) {
        if (array == null) {
            return null;
        }
        // 分组间隔
        int interval = array.length / 2;
        // 决定分组的间隔，当间隔为1时，就相当于一遍直接插入排序
        while (interval > 0) {
            // 对序列进行分组
            for (int start = 0; start < interval; start++) {
                // 对每个分组进行直接插入排序
                for (int i = start + interval; i < array.length; i+=interval) {
                    int temp = array[i];
                    int j = i - interval;
                    // 将比 array[i] 大的元素向右移
                    while (j >= start && array[j] > temp) {
                        array[j + interval] = array[j];
                        j -= interval;
                    }
                    // 找到 array[i] 元素该插入的位置，存取该元素
                    array[j + interval] = temp;
                }
            }
            // 缩小间隔
            interval /= 2;
        }
        System.out.println(Arrays.toString(array));
        return array;
    }
}
